package tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {

    static class TreeNode{
        public char val;
        public TreeNode leftChild;
        public TreeNode rightChild;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public int nodeSize;

    //public TreeNode root;

    /**
     * 创建一棵树，创建之后返回根节点
     * @return
     */
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.leftChild = B;
        A.rightChild = C;
        B.leftChild = D;
        B.rightChild = E;
        C.leftChild = F;
        C.rightChild = G;
        E.rightChild = H;

        return A;

    }

    // 前序遍历 根左右
    public void preOrder(TreeNode root) {
        if (root == null){
            return;//空树，直接返回
        }

        System.out.print(root.val+" ");
        preOrder(root.leftChild);
        preOrder(root.rightChild);
    }

    public void preOrderNor(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur = cur.leftChild;
            }
            TreeNode top = stack.pop();
            cur = top.rightChild;
        }

    }
    // 中序遍历 左根右
    public void inOrder(TreeNode root) {
        if (root == null){
            return;//空树，直接返回
        }
        inOrder(root.leftChild);
        System.out.print(root.val+" ");
        inOrder(root.rightChild);
    }
    public void inOrderNor(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.leftChild;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val+" ");
            cur = top.rightChild;
        }

    }
    // 后序遍历 左右根
    public void postOrder(TreeNode root) {
        if (root == null){
            return;//空树，直接返回
        }
        postOrder(root.leftChild);
        postOrder(root.rightChild);
        System.out.print(root.val+" ");

    }
    TreeNode prev = null;
    public void postOrderNor(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.leftChild;
            }
            TreeNode top = stack.peek();
            if(top.rightChild == null || top.rightChild == prev){
                System.out.print(top.val+" ");
                stack.pop();
                prev = top;
            }else{
                cur = top.rightChild;
            }
        }




    }

    //遍历
    public int size(TreeNode root){
        if (root == null){
            return 0;
        }
        nodeSize++;
        size(root.leftChild);
        size(root.rightChild);
        return nodeSize;
    }

    //子问题解决
    public int size2(TreeNode root){
        if (root == null){
            return 0;
        }
        return size2(root.leftChild)+size2(root.rightChild)+1;
    }

    public int rootSize;
    // 获取叶子节点的个数

    /**
     * 遍历
     * @param root
     * @return
     */
    public int getLeafNodeCount(TreeNode root){
        if (root == null){
            return 0;
        }
        if (root.rightChild == null && root.leftChild == null){
            rootSize++;
        }
        getLeafNodeCount(root.leftChild);
        getLeafNodeCount(root.rightChild);
        return rootSize;

    }

    /**
     * 子问题思路-求叶子结点个数
     * @param root
     * @return
     */
    public int getLeafNodeCount2(TreeNode root){
        if (root == null){
            return 0;
        }
//        if (root.leftChild == null && root.rightChild == null){
//            return 1;
//        }

        return getLeafNodeCount2(root.leftChild)+getLeafNodeCount2(root.rightChild)+
                (root.leftChild == null && root.rightChild == null ? 1 : 0);
    }

    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k){
        if (root == null)
        {
            return 0;
        }
//        if (k == 1){
//            return 1;
//        }
        return getKLevelNodeCount(root.leftChild,k-1)
                + getKLevelNodeCount(root.rightChild,k-1)
                + (k == 1 ? 1 : 0);
    }
    // 获取二叉树的高度
    int getHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        return Math.max(getHeight(root.leftChild),getHeight(root.rightChild))+1;
    }
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, int val){
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        return find(root.leftChild,val) == null ? find(root.rightChild,val) : find(root.leftChild,val);
    }

    TreeNode find(TreeNode root, char val){
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;//找到了返回
        }
//        TreeNode ret = find(root.leftChild,val);
//        if(ret != null){
//            return ret;
//        }
//        TreeNode ret2 = find(root.leftChild,val);
//        if(ret2 != null){
//            return ret2;
//        }
        return find(root.leftChild,val) == null ? find(root.rightChild,val) : find(root.leftChild,val);//左树没找到找右边

    }
    //层序遍历
    //巧用队列
    public void levelOrder(TreeNode root){
        if (root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode tmp = null;
        queue.offer(root);
        while(!queue.isEmpty()){
            //此处可以直接poll
            tmp = queue.peek();
            System.out.print(tmp.val+" ");
            if (tmp.leftChild != null){
                queue.offer(tmp.leftChild);
            }
            if (tmp.rightChild != null){
                queue.offer(tmp.rightChild);
            }
            queue.poll();
        }



    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.leftChild);
                queue.offer(cur.rightChild);

            }else{
                break;//结束这个循环
            }
        }
        while(!queue.isEmpty()){
            //一个元素 一个元素 出队，来判断是不是null
            TreeNode tmp = queue.peek();
            if (tmp == null){
                queue.poll();
            }else{
                return false;
            }
        }
        return true;
        //需要判断队列当中是否有非空的元素
//        if(root.leftChild == null && root.rightChild != null){
//            return false;
//        }
//        return isCompleteTree(root.leftChild) && isCompleteTree(root.rightChild);
    }


}
